package day_2023_7_to_10;

import javafx.util.Pair;

/**
 * @author haomin
 * @date 2023/09/06 23:59
 **/
public class Day_9_6 {
    class Solution {
        public TreeNode lcaDeepestLeaves(TreeNode root) {
            return f(root).getKey();
        }

        private Pair<TreeNode, Integer> f(TreeNode root) {
            if (root == null) {
                return new Pair<>(root, 0);
            }

            Pair<TreeNode, Integer> left = f(root.left);
            Pair<TreeNode, Integer> right = f(root.right);

            if (left.getValue() > right.getValue()) {
                return new Pair<>(left.getKey(), left.getValue() + 1);
            }
            if (left.getValue() < right.getValue()) {
                return new Pair<>(right.getKey(), right.getValue() + 1);
            }
            return new Pair<>(root, left.getValue() + 1);
        }
    }
}